#ifndef __COMMON_HPP__
#define __COMMON_HPP__
// 公有的类 - 存放公共的头文件以及函数类型等

#include <iostream>
#include <cassert>
#include <mutex>
#include <unordered_map>

#ifdef _WIN32
#include <Windows.h>
#else  // Linux
#endif

namespace QiHai
{
	static const size_t MAX_BYTES = 256 << 10;  // 256 * 1024byte 小于等于按照三层模型申请内存
	static const size_t NFREELIST = 208;  // ThreadCache/CentralCache哈希桶的个数
	static const size_t SHIFT_PAGE = 13;  // 一页为 8 * 1024kb = 2^13 byte
	static const size_t NPAGES = 128;  // 限制pagecache插入哈希桶的适合最大的页数为128page = 1MB

	inline static void* SystemAlloc(size_t kpage)
	{
#ifdef _WIN32
		void* ptr = VirtualAlloc(NULL, kpage << SHIFT_PAGE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
		// Linux
#endif
		return ptr;  // 可以做异常处理的
	}

	// 利用系统系统调用接口释放申请的内存块 利用条件编译实现跨平台
	inline static void SystemFree(void* ptr)
	{
#ifdef _WIN32
		VirtualFree(ptr, 0, MEM_RELEASE);
#else
		// linux下brk mmap等
#endif
	}

	// 传给我一个地址，（必须是大于指针大小的哦），返回其中存储的地址
	inline static void*& NextObj(void* res)
	{
		return *((void**)res);  // 此时返回是此地址指针指向的位置
	}

	//  为了区分不同的类型，给每个类型特定的一个对齐类型，让内碎片控制到最小，也用于设置ThreadCache种哈希桶的映射规则
	class SizeClass
	{
		//0~256kb
		// 简化tcmalloc的对齐规则 - 保持每个区域最多只有10%的内存浪费
		// 申请字节数范围	              对齐字节数          哈希桶编号			     注意对齐字节数为对应数的倍数(比如如果是9byte 对应字节数为16byte)
		// [1, 128]2^7                8byte              freeList[0, 15]   16
		// [128+1, 1024]2^10          16byte             freeList[16, 71]  56
		// [1024+1, 8*1024]2^13       128byte		     freeList[72, 127] 56
		// [8*1024+1, 64*1024]2^16    1024byte           freeList[128, 183]56
		// [64*1024+1, 256*1024]2^18  8*1024byte         freeList[184, 207]24
	public:
		static size_t RoundUp(size_t bytes); // 向上对齐数
		static size_t _RoundUp(size_t bytes, size_t size);
		static size_t Index(size_t bytes);
		static size_t _Index(size_t bytes, size_t size);
		static size_t NumMoveSize(size_t byte);
		static size_t NumMovePage(size_t byte);
	};

	// 自由链表-提供头插、头删、判空操作
	class FreeList
	{
	private:
		void* _head = nullptr;
		size_t _Maxsize = 1;  // 慢启动策略，size表示当前批量申请个数
		size_t _size = 0;  // 当前自由链表真正的个数
	public:
		bool Empty()
		{
			return _head == nullptr;
		}

		void Headinsert(void* res);
		void* HeadPop();
		void PushRange(void* res, size_t n);  // 插入一段
		void PopRange(void*& start, size_t n);  // 弹出一段

		size_t& getMaxSize() { return _Maxsize; }
		size_t getSize() { return _size; }
	};

	// span-内存跨度，管理一大块内存
	struct Span
	{
		size_t _pageNum = 0;  // 页号  -- 需要注意，所谓的页号，就是为了区分Span(page)之前的区别，直接拿地址除以page的大小即可。并且也是存储内存起始位置的地方
		size_t _n = 0;  // 页的个数  表示申请的是几page
		size_t _objNum = 0;  // 表示当前申请到centralcache后的具体要切分的类型大小 - 挂到对应的哈希桶上

		Span* _pre = nullptr;  // 因为在centralcache中用双链表管理每一个桶中的span对象。因为回收的时候，需要知道前一个span的位置，所以使用双链表
		Span* _next = nullptr;

		size_t _useCount = 0;  // 这里表示使用的个数  此变量用于判断此span是否回收完毕，回收完毕需要返回pagecache
		void* _freeList = nullptr;  // span挂自由链表的位置，这里是分配内存存储的地方，由centralcache操作

		bool _isUse = false;  // 是否在被使用  方便PageCache在合并的时候不能合并正在使用的span
	};

	// 管理span的双链表对象
	class SpanList
	{
	private:
		Span* _head = nullptr;
		std::mutex _mtx;// 对于centralCache来说，每个桶需要一个桶锁。桶锁的出现可以大大的提升效率。
	public:
		SpanList()
		{
			// 构造函数
			_head = new Span;
			_head->_next = _head;
			_head->_pre = _head;
		}

		// 桶锁上锁
		void lock() { _mtx.lock(); }
		// 桶锁解锁
		void unlock() { _mtx.unlock(); }

		Span* Begin() { return _head->_next; }
		Span* End() { return _head; }
		bool Empty() { return _head->_next == _head; }

		void PushBack(Span* span);  // 尾插
		Span* PopHead();  // 头pop
		void Erase(Span* span);  // 提供任意位置的弹出
	};
	
	////////////////SizeClass//////////////////////

	// bytes：类型大小 size：对齐字节数
	inline size_t SizeClass::_RoundUp(size_t bytes, size_t size)
	{
		//if (bytes % size == 0) return bytes;
		//return (bytes / size + 1) * size;
		// 使用位运算进行优化
		return ((bytes + size - 1) & ~(size - 1));
	}
	// 根据给出的类型大小，计算出向上对齐数
	inline size_t SizeClass::RoundUp(size_t bytes)
	{
		if (bytes <= 128) return _RoundUp(bytes, 8);
		else if (bytes <= 1024) return _RoundUp(bytes, 16);
		else if (bytes <= (8 << 10)) return _RoundUp(bytes, 128);
		else if (bytes <= (64 << 10)) return _RoundUp(bytes, 1024);
		//else if (bytes <= (256 << 10)) return _RoundUp(bytes, 8 << 10);
		else return _RoundUp(bytes, 8 << 10);  // 后面均以1页对齐
	}

	// bytes:类型大小  bits:对齐字节数的2的几次方的位数
	inline size_t SizeClass::_Index(size_t bytes, size_t bits)
	{
		//return (bytes + size - 1) / size - 1;
		return (((bytes + ((size_t)1 << bits) - 1) >> bits) - 1);
	}
	// 根据给出的类型大小，计算出对应的哈希桶桶号
	inline size_t SizeClass::Index(size_t bytes)
	{
		static int indexArr[] = { 16, 72, 128, 184 };  // 存储前面的哈希桶总编号，方便后续算完直接加上
		if (bytes <= 128) return _Index(bytes, 3);
		else if (bytes <= 1024) return indexArr[0] + _Index(bytes - 128, 4);
		else if (bytes <= (8 << 10)) return indexArr[1] + _Index(bytes - 1024, 7);
		else if (bytes <= (64 << 10)) return indexArr[2] + _Index(bytes - (8 << 10), 10);
		else if (bytes <= (256 << 10)) return indexArr[3] + _Index(bytes - (64 << 10), 13);
		else
		{
			// 出现问题了
			assert(false);
			return -1;
		}
	}
	// 根据传入对应类型大小的对齐大小，算出申请一批内存的上限
	inline size_t SizeClass::NumMoveSize(size_t byte)
	{
		if (byte == 0) return byte;

		size_t sizes = MAX_BYTES / byte;
		// 对于过大和过小做出判断：最多有512份 最少2份
		if (sizes > 512) sizes = 512;
		if (sizes < 2) sizes = 2;
		return sizes;
	}

	// 计算对应类型大小应该获取大概多少页的span
	inline size_t SizeClass::NumMovePage(size_t byte)
	{
		size_t size = NumMoveSize(byte);  // 首先算出上限
		size_t npage = size * byte;  // 相乘算出上限的总大小
		npage = npage >> SHIFT_PAGE;  // 算出页的个数
		// 此时肯定存在过小的，0就直接等于1即可
		if (npage == 0) npage = 1;
		return npage;
	}

	///////////////FreeList///////////////////

	// 头插结点
	void FreeList::Headinsert(void* res)
	{
		NextObj(res) = _head;
		_head = res;
		++_size;
	}

	// 头删结点 注意，不是真正的将此空间释放，而只是从链表中删除而已,并且弹出
	void* FreeList::HeadPop()
	{
		assert(_head);  // 防止_head为空指针

		void* head = _head;
		_head = NextObj(_head);
		--_size;
		return head;
	}

	// 插入一段自由链表
	void FreeList::PushRange(void* res, size_t n)
	{
		// 插入n个，起始地址为res
		void* begin = res;
		int i = 1;  // 进行调试所用的变量
		while (res && NextObj(res))
		{
			i++;
			res = NextObj(res);
		}
		assert(i == n);  // 这里出错说明上层切分的时候最后没有置空
		NextObj(res) = _head;
		_head = begin;
		_size += n;
	}

	// 弹出一段自由链表  从头开始向后弹出哦
	void FreeList::PopRange(void*& start, size_t n)
	{
		assert(_size >= n);  // 必须得保证的哦

		start = _head;
		void* res = _head;
		for (size_t i = 0; i < n - 1; ++i)
		{
			res = NextObj(res);
		}

		_head = NextObj(res);
		NextObj(res) = nullptr;  // 截断准备上传哦
		_size -= n;
	}

	/////////////SpanList///////////////

	// 尾插入此双链表中
	void SpanList::PushBack(Span* span)
	{
		_head->_pre->_next = span;
		span->_pre = _head->_pre;
		_head->_pre = span;
		span->_next = _head;
	}

	// 将此位置弹出
	void SpanList::Erase(Span* span)  
	{
		assert(span != _head);

		span->_pre->_next = span->_next;
		span->_next->_pre = span->_pre;
		span->_pre = span->_next = nullptr;
	}

	// 将第一个span弹出
	Span* SpanList::PopHead()
	{
		Span* res = Begin();
		Erase(res);
		return res;
	}

}

#endif // !__COMMON_HPP__
